The term "net" as used herein refers to a conductive region connecting components of a user's circuit design. For example, one net may connect the output terminal of an AND gate to the input terminal of another AND gate and to the input terminal of a flip flop. An AND gate is one component type. A flip flop is another component type. An "instance" is a single occurrence of a component type. A "netlist" is a list of all the nets which connect the component instances of a user's design and the component instances connected by each net.
Field programmable gate arrays (FPGAs) may be programmed to implement one of many different integrated circuit (IC) designs. Typically, these designs are provided by a customer in the form of design and timing constraints. Using the design and timing constraints, code is created that, when run, controls the programming of the FPGA.
During this process, a place and route operation is performed to configure an FPGA to a circuit that implements the customer design. If it is determined that after a place and route operation is performed a change to the design is required, both the design and the place and route processes are repeated from the beginning. Generally, it is desirable to avoid having to repeat the entire place and route process from the beginning because it can be very time consuming, both in man hours and system time.
One solution to avoid repeating the entire place and route process is to only re-implement the parts of the design that changed from the previous place and route cycle. Although this may be fairly straight forward when using schematics (because changes to a schematic cause very little change in a netlist), it is more difficult when the design has been generated through the use of logic synthesis and high-level languages.
In synthesis, user-entered design information consists of functional descriptions written in typically either Verilog or VHDL, and accompanying implementation scripts which document side information, such as timing constraints and design-tool specific commands (e.g., effort levels, mapping strategies, library selection, etc.). Therefore, when using synthesis, a user is not working with the primitives that eventually undergo placement and routing. Instead, a user is working in a high-level language which is translated to low-level primitives by a synthesizer. The low-level implementation of a design is not under the direct control of the user and contains nets and architectural primitives which cannot be easily related back to the original high-level description.
The typical synthesis design flow comprises initially creating a language-based functional design and imposing timing constraints on the design. Then, this high-level design is synthesized into architectural primitives and a netlist is generated (and possibly feed-forward timing information). Next, physical implementation occurs in the FPGA-specific design system based on the netlist. Following the physical implementation, back-annotation of the actual performance of the resulting implementation occurs. Thereafter, if necessary, an iteration of the mapping/implementation cycle may be performed to ensure that all the user-specified timing constraints are satisfied.
When portions of a design are to be changed, either as a result of a design change or to improve performance, the user in logic synthesis is only able to make changes to the high-level language description that produces the new design. When the changed high-level language description is resynthesised, the low-level netlist may be created with completely different instance names and net names, even when the "old" and "new" netlists are substantially the same from a functional point of view. In other words, even though the new design is functionally quite similar to the old design, the low-level netlists generated from both are radically different in terms of net names and instance names. Thus, the low-level netlists cannot easily be related to the original high-level design. Such a correspondence between the new and old topologies would be desirable in the synthesis environment in order to try to preserve as much of the layout, placement and routing as possible. This would permit an incremental design change to be made without changes to the implementation of unaffected areas. This would typically result in a faster physical implementation time.
Several authors have described methods for comparing netlists, a variant of a more general problem known as "graph isomorphism". Rick Spickelmier ("WOMBAT: A New Netlist Comparison Program", Rick L. Spickelmier and A. Richard Newton, IEEE International Conference on Computer Aided Designer, 1983, pp. 170-171) and Carl Ebeling ("Validating VLSI Circuit Layout by Wirelist Comparison", Carl Ebeling and Ofer Zajicek, IEEE International Conference on Computer Aided Design, 1983, pp. 172-173) both describe programs for determining whether or not integrated circuit (IC) layouts match their schematics by using a netlist verification process. When performing this determination, netlists were generated corresponding to the actual IC layout and corresponding to its schematic. The net and instance names of both netlists did not correspond to each other. After performing the comparison process, a determination of whether the IC matched the schematic resulted. Today, several commercial products are available for performing layout to schematic comparison.
The present invention provides for using a netlist comparison as part of an incremental design process. The results of the netlist comparison is actively used to control the implementation process, as opposed to solely providing a form of verification.